//
// Created by wangwanlong on 2024/12/2.
//

#ifndef TEST_PY_DESENT_REFINER_H
#define TEST_PY_DESENT_REFINER_H
#include "refiner_base.h"
#include "fast_reset_flag_array.h"
#include "policies/stop_policy.h"
#include "mandatory.h"
//n-level局部搜索
namespace mcgpp{
  template<class StoppingPolicy = Mandatory>
  class DesentRefiner : public RefinerBase {
  public:
    DesentRefiner(ds::GenericGraph &graph) : RefinerBase(graph),
                                             _marked(graph.initialNumNodes()){
      _performed_moves.reserve(graph.initialNumNodes());

    }
    void initializeImpl() override {
      _marked.reset();
      _stopping_policy.resetStatistics();//初始化停止策略
    }

    //刚还原的顶点执行局部搜索
    void  refineImpl(std::vector<IDType>& refine_nodes, Metrics& f_best) override{
      for(auto v : refine_nodes){
        if(isBorderNode(v))
          cut_nodes.add(v);
      }

      metrics::conductance(_g,f_best);

//      LOG<<"check1";
//      checkDataStructure(f_best);


      Metrics new_obj;
      Metrics better_obj;
      int cnt = 0;
      int best_v = -1;

      int min_cond_index = -1;
      const double beta = log(_g._current_num_nodes);
      current_obj = f_best;
      _performed_moves.clear();
      _marked.reset();
      _stopping_policy.resetStatistics();//初始化停止策略

      while(cut_nodes.size() && !_stopping_policy.searchShouldStop(beta)){
        //从边界顶点中找到最优的
        better_obj.reset();
        for(auto v : cut_nodes){
          ll delta = moveNodeGain(v, _g.partID(v), 1 ^ _g.partID(v), current_obj, new_obj);
          if (delta == invalidGain)//确保移动都是有效的
            continue;

          if (new_obj < better_obj) {
            //选择最优的或者等概率最小的接受
            best_v = v;
            better_obj = new_obj;
            cnt = 0;
          } else if (new_obj == better_obj && Randomize::instance().getRandomInt(0, ++cnt) == 0)
            best_v = v;
        }

        //1.标记顶点并且更新停止条件
        _marked.set(best_v);
        _stopping_policy.updateStatistics(better_obj.conductance);//double还是ll?
        //2.执行移动
        current_obj = better_obj;
        changeNodePart2(best_v, _g.partID(best_v), 1 ^ _g.partID(best_v));
        _performed_moves.push_back(best_v);

        if(current_obj < f_best){
          //保存最优解
          f_best = current_obj;
          min_cond_index = _performed_moves.size() - 1;//记录最优电导位置
          _stopping_policy.resetStatistics();//重置停止条件

        }
      }

      //回滚到最优解
      rollback(_performed_moves.size() - 1, min_cond_index);
//      LOG<<"check2";
//      checkDataStructure(f_best);

    }


    void changeNodePart2(IDType v, PartitionID from, PartitionID to) {
      _g.changeNodePart(v, from, to, cut_nodes, _marked);

      cut_nodes.remove(v);//v已经移动过了，不再考虑它的移动

    }

    void checkDataStructure(Metrics& obj) {
//      //检查每个点的weight计算
      _g.check();
//      //检查切点
//      int cut_node_count = 0;
//      for (auto v: _g._current_node_set) {
//        if (isBorderNode(v)) {
//          ++cut_node_count;
//          if (!cut_nodes.contains(v))
//            ERROREXIT("cut node error!");
//        }
//      }
//      if (cut_node_count != cut_nodes.size())
//        ERROREXIT("cut node count error!");
//
      // 检查解是否有问题
      ll cut_num = 0, cut_weight = 0;
      Vec<ll> partInfo_num(2), partInfo_weight(2), partInfo_t_weight(2);
      for (auto v: _g._current_node_set) {
        int pid = _g.partID(v);
        partInfo_num[pid] += _g.node(v).total_edge_num;
        partInfo_weight[pid] += _g.node(v).total_edge_weight;
        partInfo_t_weight[pid] += _g.node(v).weight();
      }
      for (int i = 0; i < _g._num_edges; ++i) {
        if (_g.edgeIsEnabled(i) && _g._connectivity_sets[i].bit() == 3) {
          cut_weight += _g.edge(i).weight();
          cut_num += 1;
        }
      }
      ll volume = 0;
      switch (Context::instance().objMetric) {
        case ObjMetric::cut_num:
          if (cut_num != obj.cut_num) {
            LOG << "cut num:" << cut_num << obj.cut_num;
            metrics::conductance(_g);
            ERROREXIT("cut num error!");
          }
          if (partInfo_num[0] != _g._part_info[0].num || partInfo_num[1] != _g._part_info[1].num) {
            LOG << partInfo_num[0] << partInfo_num[1];
            LOG << _g._part_info[0].num << _g._part_info[1].num;
            ERROREXIT("part info num error!");
          }
          {
            volume = std::min(partInfo_num[0], partInfo_num[1]);
            if (volume != obj.volume_num) {
              LOG << volume << obj.volume_num;
              ERROREXIT("volume num error!");
            }
            ll cond = (static_cast<double>(cut_num) / static_cast<double>(volume)) * 1e10;
            if (cond != obj.conductance)
              ERROREXIT("cond error!");
          }
          break;
        case ObjMetric::cut_weight:
          if (cut_weight != obj.cut_weight) {
            LOG << "cut weight:" << cut_weight << obj.cut_weight;
            metrics::conductance(_g);
            ERROREXIT("cut weight error!");
          }
          if (partInfo_weight[0] != _g._part_info[0].weight || partInfo_weight[1] != _g._part_info[1].weight) {
            LOG << partInfo_weight[0] << partInfo_weight[1];
            LOG << _g._part_info[0].weight << _g._part_info[1].weight;
            ERROREXIT("part info weight error!");
          }
          {
            volume = std::min(partInfo_weight[0], partInfo_weight[1]);
            if (volume != obj.volume_weight) {
              LOG << volume << obj.volume_weight;
              ERROREXIT("volume weight error!");
            }
            ll cond = (static_cast<double>(cut_weight) / static_cast<double>(volume)) * 1e10;
            if (cond != obj.conductance)
              ERROREXIT("cond error!");
          }
          break;
        case ObjMetric::real:
          if (cut_weight != obj.cut_weight) {
            LOG << "cut weight:" << cut_weight << obj.cut_weight;
            metrics::conductance(_g);
            ERROREXIT("cut weight error!");
          }
          if (partInfo_t_weight[0] != _g._part_info[0].t_weight || partInfo_t_weight[1] != _g._part_info[1].t_weight) {
            LOG << partInfo_t_weight[0] << partInfo_t_weight[1];
            LOG << _g._part_info[0].t_weight << _g._part_info[1].t_weight;
            ERROREXIT("part info t weight error!");
          }
          {
            volume = std::min(partInfo_t_weight[0], partInfo_t_weight[1]);
            if (volume != obj.volume_t_weight) {
              LOG << volume << obj.volume_t_weight;
              ERROREXIT("volume weight error!");
            }
            ll cond = (static_cast<double>(cut_weight) / static_cast<double>(volume)) * 1e10;
            if (cond != obj.conductance)
              ERROREXIT("cond error!");
          }
          break;
        default:
          ERROREXIT("obj metric error!");
      }
    }


    void rollback(int last_index, const int min_cond_index) {

      while (last_index != min_cond_index) {
        IDType v = _performed_moves[last_index];
        changeNodePart(v, _g.partID(v), (_g.partID(v) ^ 1));
        --last_index;
      }
    }


    //移动点v后，更新其邻居
    void updateNeighbor(IDType v){

    }



    std::vector<IDType> _performed_moves;//记录移动的顶点，用来回归到最优电导
    StoppingPolicy _stopping_policy;//停止策略
    ds::FastResetFlagArray<>_marked;//用于标记点
  };


}
#endif //TEST_PY_DESENT_REFINER_H
